package com.mjf.sort;

import java.util.Arrays;

/**
 * 希尔排序(缩小增量排序)
 *
 * @see ShellSort#shellSortWithExchange(int[]) 希尔排序【交换法】
 * @see ShellSort#shellSortWithMovePosition(int[]) 希尔排序【移位法】
 */
public class ShellSort {

    public static void main(String[] args) {

        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("排序前: " + Arrays.toString(arr));
//        shellSortWithExchange(arr); // 交换法
        shellSortWithMovePosition(arr); // 移位法
        System.out.println("排序后: " + Arrays.toString(arr));
    }

    /**
     * 希尔排序【交换法】
     * <p>
     * 思路：<br>
     * 1.初始增量gap(arr.length/2)，意味着将数组分为gap组。[0, gap],[1, gap+1]...<br>
     * 2.从后往前对组内元素进行比较，如果前面元素小于后面元素则对他们进行交换<br>
     * 3.然后缩减增量gap=gap/2，重复以上步骤，直到gap缩减为0
     *
     * @param arr 待排序数组
     */
    public static void shellSortWithExchange(int[] arr) {
        int gap = arr.length / 2;  // 组数(间隔)
        int sortCnt = 0;    // 排序次数
        int temp;

        while (gap > 0) {
            // 共遍历gap次
            for (int i = arr.length - 1; i >= gap; i--) {
                // 遍历各组中的元素，共gap组，每组arr.length/gap个元素，步长为gap
                for (int j = i; j - gap >= 0; j -= gap) {
                    // 如果减去步长后的元素大于当前元素，就交换
                    if (arr[j - gap] > arr[j]) {
                        temp = arr[j];
                        arr[j] = arr[j - gap];
                        arr[j - gap] = temp;
                    }
                }
            }
            gap = gap / 2;
//            System.out.printf("第%d次排序后的结果为%s\n", ++sortCnt, Arrays.toString(arr));
        }
    }

    /**
     * 希尔排序【移位法】
     * <p>
     * 思路：<br>
     * 1.初始增量gap(arr.length/2)，意味着将数组分为gap组。[0, gap],[1, gap+1]... <br>
     * 2.对每组元素使用直接插入排序<br>
     * 3.然后缩减增量gap=gap/2，重复以上步骤，直到gap缩减为0
     *
     * @param arr 待排序数组
     */
    public static void shellSortWithMovePosition(int[] arr) {
        int gap = arr.length / 2;  // 组数(间隔)
        int sortCnt = 0;    // 排序次数
        int insertVal;  // 待插入元素
        int insertIndex;    // 待插入索引

        while (gap > 0) {
            // 从第gap个元素开始遍历（gap之前元素为有序表），逐个对其所在组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                insertVal = arr[i];
                insertIndex = i - gap;
                while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                    arr[insertIndex + gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                arr[insertIndex + gap] = insertVal;
            }
            gap = gap / 2;
//            System.out.printf("第%d次排序后的结果为%s\n", ++sortCnt, Arrays.toString(arr));
        }
    }

}
